package com.cyy.test_t_3_;


import com.cyy.test.util.ListNode;

/**
 * 剑指Offer 面试题37
 * 两个链表的第一个公共结点
 * 题目描述:
 * 输入两个链表，找出它们的第一个公共结点。
 */
public class t_37 {
	/**
	 * 这两个链表是单链表，如果有公共结点，那么从这一个结点开始，
	 * 它们的next都指向同一个结点。但是由于是单向链表的结点，每
	 * 个节点只有一个next，因此从第一个公共结点开始，之后它们所
	 * 有结点都是重合的，不可能出现分叉。 
	 */
	public static void main(String[] args) {
		ListNode p1 = new ListNode(1);
		ListNode p2 = new ListNode(2);
		ListNode p3 = new ListNode(3);
		ListNode p4 = new ListNode(4);
		ListNode p5 = new ListNode(5);
		ListNode p6 = new ListNode(6);
		
		p1.next = p2;
		p2.next = p3;
		p3.next = p4;
		p4.next = p5;
		p6.next = p3;
		
		ListNode res = FindFirstCommonNode(p1,p6);
		while(res != null){
			System.out.println(res.val);
			res = res.next;
		}
		
	}
	
	public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		if(pHead1 == null || pHead2 == null){
			return null;
		}
		
		//记录它们的长度可以不用两个辅助栈，让长的先走，可以同时到链尾
		int nLen1 = GetListLength(pHead1);
		int nLen2 = GetListLength(pHead2);
		int nLenDif = nLen1 - nLen2;
		
		//不妨假定pHead1较长
		ListNode pListHeadLong = pHead1;
		ListNode pListHeadShort = pHead2;
		if(nLen2 > nLen2){
			pListHeadLong = pHead2;
			pListHeadShort = pHead1;
			nLenDif = nLen2 - nLen1;
		}
		
		//先在长链表上走几步，再同时在两个链表上遍历
		for(int i = 0; i < nLenDif; i ++){
			pListHeadLong = pListHeadLong.next;
		}
		
		while((pListHeadLong != null) && (pListHeadShort != null)
				&& (pListHeadLong != pListHeadShort)){
			pListHeadLong = pListHeadLong.next;
			pListHeadShort = pListHeadShort.next;
		}
		
		//得到第一个公共结点
		return pListHeadLong;
	}

	private static int GetListLength(ListNode pHead) {
		int nLen = 0;
		ListNode pNode = pHead;
		while(pNode != null){
			++ nLen;
			pNode = pNode.next;
		}
		return nLen;
	}

}
